11088 - End up with more teams/11088.2.cpp

   1 /*
   2   Problem: 11088 - End up with More Teams
   3   Author: Andrés Mejía-Posada
   4
   5   Trying another approach...
   6   Works, but slower. Accepted
   7  */
   8
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27 using namespace std;
  28
  29 #define D(x) cout << #x " is " << x << endl
  30 #define bit(i, n) (n & (1 << i))
  31
  32 int memo[1<<15], x[15], n;
  33
  34 /*
  35   Returns the maximum amount of teams that can be made using
  36   teams set on on bitwise mask avail. At each step, I try to
  37   build a new team using all possible valid triplets.
  38 */
  39 int best(int avail){
  40   int &ans = memo[avail];
  41   if (ans == -1){
  42     ans = 0;
  43     for (int i=0; i<n; ++i)
  44       if (bit(i, avail))
  45         for (int j=i+1; j<n; ++j)
  46           if (bit(j, avail))
  47             for (int k=j+1; k<n; ++k)
  48               if (bit(k, avail))
  49                 if(x[i] + x[j] + x[k] >= 20)
  50                   ans = max(ans, 1 + best(avail & ~(1 << i) & ~(1 << j) & ~(1 << k))); //Make team (i, j, k).
  51   }
  52   //printf("best(%X) = %d\n", avail, ans);
  53   return ans;
  54 }
  55
  56 int main(){
  57   int pizza = 1;
  58   while (scanf("%d", &n) == 1 && n){
  59     for (int i = 0; i<n; ++i) scanf("%d", &x[i]);
  60
  61     memset(memo, -1, sizeof memo);
  62     printf("Case %d: %d\n", pizza++, best((1 << n) - 1));
  63   }
  64
  65   return 0;
  66 }